Information, including data information, is conveniently communicated over communication channels. These channels may include one or more paths between entities allowing communication of information through one or more types of communication media, for example: wire line, fibre optic cables and wireless connections. Typically, a communication channel has a finite bandwidth, i.e., only a finite amount of information may be communicated through the channel in a given amount of time. Information from several sources may be communicated over a common communication channel by sequencing the information over time.
Different types of information may be subject to different communication requirements. Examples of such requirements include a minimum amount of bandwidth, a maximum amount of permissible delay, and a maximum permissible portion of the information that is not successfully communicated. For example, a teleconferencing application may require communication of information at high bandwidth and with very little delay but may not be seriously degraded if a portion of the information is lost during transmission. Another application, for example an interactive web browsing application, may tolerate greater delay but with little or no tolerance for lost information. As another example, file transfer application may tolerate substantial delay but require complete reliability of the information communicated. Thus, it is desirable to provide communication in a manner that accommodates the various communication requirements of various types of information. It is also useful to be able to fairly allocate communication resources among types of information having similar communication requirements.
Attempts have been made to use calendar structures for the allocation of information to communication channels. However, such calendar structures have generally required storing and processing large amounts of overhead information to control the communication of information through a communication channel. Such requirements have placed limits on the operating speed of the system used to allocate information to the channel. Thus, scheduling and servicing techniques that avoid these disadvantages are desired.
A typical prior art scheduler architectures is a traditional n-slot weighted fair queuing (WFQ) calendar which may contain hundreds of calendar slots in order to meet the diversified bandwidth requirements and variable packet sizes. In view of this, a large amount of memory is required for implementation and this large memory requirement leads to latency issues.
U.S. patent application Ser. No. 10/334,204 filed Dec. 30, 2002 to Olesinski et al., describes one prior art calendar structure. In the Ser. No. 10/334,204 application entitled “Methods and Apparatus for Scheduling and Servicing Events Using a Calendar Structure” a multi-tier structure is presented which means that it consumes less memory than a typical n-slot WFQ calendar. Although it does not require hundreds of calendar slots as in the n-slot WFQ calendar it still requires tens of calendar slots which as indicated previously raises latency issues. The contents of application Ser. No. 10/334,204 are incorporated herein by reference.
One additional problem that exists with both n-slot WFQ calendars and the architecture disclosed in the aforementioned application is that the number of calendar slots in a calendar is fixed. This means that even if some calendar slots are never used the memory used for implementing them is reserved.
In a typical WFQ calendar architecture each calendar slot has to store both head and tail pointers. The more slots required, the more memory is used to store these head and tail pointers. This is a particular issue because internal memory is often used in the implementation to minimize latency. This need to use internal memory is significant for WFQ schedulers that may be implemented in the datapath. For example, a traffic management chip designed in Alcatel supports 3.5 k WFQ calendars and consumes around 4 M bits internal memory. It was desired that further 2 k WFQ calendars be implemented on the chip but this is not feasible due to the large amount of internal memory consumption.
The present invention addresses the aforementioned problems by using resources in a very efficient way while maintaining good performance. Fairness of scheduling and service is provided by using a two-slot dynamic length WFQ calendar. The calendar can be configured to provide a fine granularity by using a hierarchical WFQ scheme.